package company;

/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * <p>
 * 每一步只能移动到下一行中相邻的结点上。
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 * 示例 1：
 * <p>
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 * 2
 * 3 4
 * 6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * 示例 2：
 * <p>
 * 输入：triangle = [[-10]]
 * 输出：-10
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 分析：
 * triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 转为二维数组
 * int[][] triangle =
 * {[2]
 * [3,4]
 * [6,5,7]
 * [4,1,8,3]
 * }
 */
public class MinimumTotal {
    public static void main(String[] args) {
        // 将输入转为二维数组
        Scanner scanner = new Scanner(System.in);
        // [[2],[3,4],[6,5,7],[4,1,8,3]]
        String s = scanner.nextLine();
        String replace = s.replace("[[", "");
        String replace1 = replace.replace("]]", "");
        String[] splitStr = replace1.split("\\],\\[");

        List<List<Integer>> triangle = new ArrayList<>();

        // 二维数组的组装
        for (int i = 0; i < splitStr.length; i++) {
            String[] s1 = splitStr[i].split(",");
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < s1.length; j++) {
                list.add(Integer.parseInt(s1[j]));
            }
            triangle.add(list);
        }
        System.out.println(minimumTotal(triangle));
    }
    public static int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        int col = triangle.get(row-1).size();
       int[] min = new int[col];
        List<Integer> integers = triangle.get(row - 1);
        // 将最后一行赋值给min作为遍历row-2时候的基数
        for (int i = 0; i < col; i++) {
            min[i] = integers.get(i);
        }
        // 从倒数第二行开始遍历，改写min，保留最后一次计算的最短路径
        for (int i = row-2; i>=0; i--) {
            List<Integer> integers1 = triangle.get(i);
            for (int j = 0; j < triangle.get(i).size(); j++) {
                min[j] = integers1.get(j)+Math.min(min[j],min[j+1]);
            }
        }
        return min[0];
    }
}

